package com.list88zhu.android.sunflower.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * <pre><code>
 *
 *  </code></pre>
 *
 * @author zhuyingming@qmtv.com
 * @date 2018/9/19
 */
public class BinarySortTree {


    private static List<Node> nodes = new ArrayList<>();
    private static Node mRootNode;
    private static int size = 0;
    private static int[] list = new int[]{50, 30, 70, 10, 40, 90, 80, 20, 0, 60};

    public static void main(String[] args) {
        for(int i = 0; i < 10; i++) {
            Node node = new Node();
            node.data = list[i];
            nodes.add(node);
        }
        createBinarySortTree(nodes);
        preResearch(mRootNode);
    }




    private static void createBinarySortTree(List<Node> nodeList) {
        for(int i = 0; i < nodeList.size(); i++) {
            insertNode(nodeList.get(i));
        }
    }


    private static void insertNode(Node node) {
        if (mRootNode == null) {
            mRootNode = node;
            return;
        }
        Node currentNode = mRootNode;
        while (true) {
            if (node.data <= currentNode.data) {
                if (currentNode.left == null) {
                    currentNode.left = node;
                    size++;
                    return;
                }
                currentNode = currentNode.left;

            }else {
                if (currentNode.right == null) {
                    currentNode.right = node;
                    size++;
                    return;
                }
                currentNode = currentNode.right;
            }
        }
    }


    /**
     * 中序遍历  根节点中间
     * @param node
     */
    public static void midResearch(Node node) {
        if (node != null) {
            midResearch(node.left);
            System.out.println(node.data);
            midResearch(node.right);
        }
    }

    public static void preResearch(Node node) {
        if (node != null) {
            System.out.println(node.data);
            preResearch(node.left);
            preResearch(node.right);
        }
    }

    public static void nextResearch(Node node) {
        if (node != null) {
            nextResearch(node.left);
            nextResearch(node.right);
            System.out.println(node.data);
        }
    }

    public static void levelResearch(Node node) {
        if (node != null) {
            System.out.println(node.data);

            nextResearch(node.left);
            nextResearch(node.right);

        }
    }



    static class Node {
        public int data;
        public Node left;
        public Node right;
    }

}
